//Queue.h

#ifndef _QUEUE_H
#define _QUEUE_H

#include <assert.h>
#include <windows.h>


template <class T>
class Queue{
public:
	DWORD ULong;

	class Node{
	private:
		friend Queue;
		Node* next;
		T object;
	public:
		Node():object()
		{
			next = 0;
		}
		Node(const T& object):object(object)
		{
			next = 0;
		}
		Node(const Node& source):object(source.object)
		{
			this->next = source.next;
		}
		~Node()
		{
		}

		Node& operator = (const Node& source)
		{
			this->object = source.object;
			this->next = source.next;

			return (*this);
		}
		T& GetObject()const
		{
			return const_cast<T&>(this->object);
		}
	};

private:
	DWORD length;
	Node* front;
	Node* rear;
public:
	Queue();
	Queue(const Queue& source);
	virtual ~Queue();
	Queue& operator = (const Queue& source);

	Node* Put(const T& object);
	T Get();
	bool IsEmpty();

	DWORD GetLength();
};

template <class T>
DWORD Queue<T>::GetLength()
{
	return this->length;
}

template <class T>
Queue<T>::Queue()
{
	this->front = 0;
	this->rear = 0;
	this->length = 0;
}

template <class T>
Queue<T>::Queue(const Queue<T> &source)
{
	this->front = 0;
	this->rear  = 0;
	if(source.front != 0)
	{
		Node* nodelink = source.front;
		this->front = new Node(nodelink->object);
		this->rear = this->front;

		for(DWORD i = 1; i < source.length; i++)
		{
			nodelink = nodelink->next;
			this->rear->next = new Node(nodelink->object);
			this->rear = this->rear->next;
		}
	}
	this->length = source.length;
}

template <class T>
Queue<T>::~Queue()
{
	if(this->front != 0)
	{
		Node* nodelink = this->front;

		for(DWORD i = 0; i < this->length; i++)
		{
			this->front = this->front->next;
			delete nodelink;
			nodelink = this->front;
		}
	}
}

template <class T>
Queue<T>& Queue<T>::operator = (const Queue& source)
{
	if(this->front != 0)
	{
		Node* nodelink = this->front;

		for(ULong i = 0; i < this->length; i++)
		{
			this->front = this->front->next;
			delete[] nodelink;
			nodelink = this->front;
		}
	}

	this->front = 0;
	this->rear = 0;

	if(source.front != 0)
	{
		Node* nodelink = source.front;
		this->front = new Node(nodelink->object);
		this->rear = this->front;

		for(ULong i = 1; i < source.length; i++)
		{
			nodelink = nodelink->next;
			this->rear->next = new Node(nodelink->object);
			this->rear = this->rear->next;
		}
	}
	this->length = source.length;
	
	return (*this);
}

template <class T>
typename Queue<T>::Node* Queue<T>::Put(const T& object)
{
	Node* nodelink;
	nodelink = new Node(object);
	if(this->front != 0)
	{
		this->rear->next = nodelink;
		this->rear = nodelink;
	}
	else
	{
		this->front = nodelink;
		this->rear = nodelink;
	}
	this->length++;

	return nodelink;
}

template <class T>
T Queue<T>::Get()
{
	assert(this->front != 0);
	T temp;

	if(this->length > 0)
	{
		temp = this->front->object;
		Node* nodelink = this->front;

		if(this->front == this->rear)
		{
			this->front = 0;
			this->rear = 0;
		}
		else
		{
			this->front = this->front->next;
		}

		if(nodelink != 0)
		{
			delete nodelink;
		}
		this->length--;
	}
	return temp;
}

template <class T>
bool Queue<T>::IsEmpty()
{
	bool result = false;
	if(this->length == 0)
	{
		result = true;
	}
	return result;
}

#endif

